/// @tags: DP
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

namespace BlueQuantum {

int const N = 1e3 + 5, M = 1e4 + 5, INF = 0x3f3f3f3f;

int n, m;
int a[N], b[N];
int f[2][M * 2];

inline void max(int &a, int b) { a < b ? a = b : 0; }

inline int main() {
  cin >> n >> m;
  int maxm = m;
  for (int i = 1; i < n; ++i) cin >> a[i] >> b[i], max(maxm, a[i] + b[i]);
  memset(f, -INF, sizeof(f));
  for (int i = 0; i < m; ++i) f[1][i] = i;
  for (int i = 1; i < n; ++i) {
    int maxx = -INF, cur = i & 1, nxt = !cur;
    for (int j = 0; j <= maxm; ++j) {
      if (j < a[i]) max(f[nxt][j + b[i]], f[cur][j] + b[i]), max(maxx, f[cur][j]);
      else if (j < a[i] + b[i])
        max(f[nxt][j - a[i]], f[cur][j]);
      else
        max(f[nxt][j], f[cur][j]);
    }
    for (int j = 0; j < b[i]; ++j) max(f[nxt][j], maxx + j);
  }
  int ans = -INF;
  for (int i = 0; i <= maxm; ++i) max(ans, f[n & 1][i]);
  cout << ans;
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("additional.in", "r", stdin);
  freopen("additional.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
